Ghi chú NP-đầy đủ

  1. ↑ Cook, S.A. (1971). The complexity of theorem proving procedures. tr. 151–158. doi:10.1145/800157.805047. Đã bỏ qua tham số không rõ |booktitle= (trợ giúp)
  2. ↑ Richard M. Karp (1972). “Reducibility Among Combinatorial Problems”. Trong R. E. Miller and J. W. Thatcher (editors) (biên tập). Complexity of Computer Computations. New York: Plenum. tr. 85–103. Liên kết ngoài trong |chapter= (trợ giúp)Quản lý CS1: văn bản dư: danh sách biên tập viên (liên kết)
  3. ↑ M.R. Garey & Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 0-7167-1045-5.Quản lý CS1: sử dụng tham số tác giả (liên kết)
Các lớp độ phức tạp quan trọng (thêm)
Các lớp được coi là giải được
DLOGTIME • AC0 • ACC0 • TC0 • L • SL • RL • NL • NC • SC • P (P-đầy đủ) • ZPP • RP • BPP • BQP 
Các lớp có thể không giải được
Các lớp được coi là không giải được
EXPTIME • NEXPTIME • EXPSPACE • ELEMENTARY • PR • R • RE • ALL
Các hệ thống cấp bậc
Các nhóm các lớp độ phức tạp